home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1994 December / PSL Monthly Shareware CD-ROM (Public Software Library)(December 1994).bin / prgmming / dos / pascal1 / rle.pas < prev    next >
Pascal/Delphi Source File  |  1993-02-03  |  17KB  |  479 lines
  1. {$D+,L+}            {debug info}
  2. {$M 8192,0,655360}  {stack size, heapmin, heapmax}
  3.  
  4. PROGRAM RunLengthEncode;
  5. {
  6.  Author:                 Ken Murphy, CIS 74025,731
  7.  Date Written:    January 1993
  8.  
  9. This program implements a Run-Length-Encoding algorithm to compress files.
  10. I wrote this to test the decompression speed and compression effect on files
  11. containing printer graphics.  These files tend to be large with long series
  12. repetitive characters.  RLE is a bad compression choice if the file to be
  13. compressed does not have runs of repetitive bytes.  The algorithm gains
  14. it's compression from reducing a series of the same byte (up to 127 of them)
  15. to 2 bytes.
  16.  
  17. Tests have proven that this RLE decompression is very fast, and it's OK to
  18. include this technique within other applications that employ files that can
  19. benefit.  Tests on my dot matrix printer graphic data files show compressions
  20. of about 65% of original size.  LZHuf compresses better, but this is faster
  21. and simpler to develop for my needs.
  22.  
  23.     The program has 3 command-line inputs in the order given:
  24.     1. Mode:  C for compress or D for Decompress
  25.     2. Input file name
  26.     3. Output file name.
  27.  
  28. The encoded data file is a series of strings.  Each string begins with a
  29. "prefix" byte.  The leftmost bit of the byte distinguishes between the two
  30. types of strings.  The remaining 7 bits in the prefix byte are a length value.
  31. The prefix byte is followed by one or more data bytes.  The two types of
  32. compressed strings are "RUN" and "LEN".  The RUN variety allows for sequences
  33. of identical bytes.  Generally, the maximum compression effect results from
  34. these.  The LEN variety accomodates sequences of data bytes that are not the
  35. same.
  36.  
  37. Here's what it looks like in a compressed file:
  38.     If the leftmost bit of the prefix byte is 1, the string is a "RUN" string.
  39.     The remaining 7 bits of the prefix byte are the replication count value
  40.     for the following data byte.  Therefore, a RUN string is always 2 bytes.
  41.  
  42.     If the leftmost bit of the prefix byte is 0, the string is a "LENGTH"
  43.     string.  The remaining 7 bits of the prefix byte are the number of
  44.     data bytes following the prefix byte.
  45.  
  46. Since the length value in the prefix byte is limited to 7 bits,  a RUN or a
  47. LENGTH can be no larger that 127 ($01 - $FF). I don't permit a length value
  48. of 0.  PASCAL will handle this type of byte as a SHORTINT.  Remember that the
  49. actual size of a RUN segment is always 2 bytes.  A LEN segment never gets
  50. larger than 128 bytes, i.e. 1 prefix byte and 127 (max) data bytes.
  51.  
  52. There's performance instrumentation kept and displayed so I can measure the
  53. algorithm and how I've coded it.
  54.  
  55. The program was developed in Borland Pascal 7.0 for a REAL target. It uses
  56. TurboPower's Object Professional, but there's no "Object Oriented"
  57. programming here.  There's not much in the way of "fancy" so it should be
  58. easy to modify to vanilla Pascal.
  59.  
  60. Also, consider this a blatant advertisement and recommendation for TurboPower's
  61. Object Professional library although I'm in no way affiliated with them.}
  62.  
  63. USES DOS, OPCrt, OPString;
  64.  
  65. CONST
  66.     MaxChars    = 127;
  67.     EndOfFile    = 100;
  68.     BufSize        =    255;
  69.  
  70. TYPE
  71.     RLE = RECORD
  72.         RepeatCount : shortint;
  73.         Data                : array[1..MaxChars] OF char;
  74.     END;
  75.  
  76.     RLE_Rec_String= array[0..MaxChars] OF char;
  77.  
  78.     SegmentTypes = (RUN, LEN);
  79.  
  80.     TimeRecord    = RECORD
  81.         Hour        :    Word;
  82.         Minute    :    Word;
  83.         Second    :    Word;
  84.         Sec100    : Word;
  85.     END;
  86.  
  87. CONST             {typed CONST}
  88.     ReadResult        : word = 0;
  89.     WriteCount        : word = 0;
  90.     Segments            : longint = 0;
  91.     TotalBytesIn    : longint = 0;
  92.     TotalBytesOut    : longint = 0;
  93.     EndInput            : boolean = false;
  94.     DisplayPrefix    : string[2] = ' ';
  95.     InputFileSize    : real = 0;
  96.     LastIBuffer        : boolean = false;
  97.     LastOBuffer        : boolean = false;
  98.     OBufferIndex    : integer = BufSize+1;
  99.     OBuffer              : string[BufSize] = '';
  100.     IBuffer                : string[BufSize] = '';
  101.     IBufferIndex    : integer = Bufsize+1;
  102.  
  103. VAR
  104.     SegmentType        : SegmentTypes;
  105.     RLE_Record        : RLE;
  106.     RLE_String        : RLE_Rec_String absolute RLE_Record;
  107.     CurrentChar     : char;
  108.     LastChar            : char;
  109.     InputFile          : FILE;
  110.     OutputFile        : FILE;
  111.     CompressMode    : boolean;
  112.     InputFileName : string;
  113.     OutputFileName: string;
  114.     OldPct                : string[7];
  115.     Started                : TimeRecord;
  116.     Stopped                : TimeRecord;
  117.  
  118. {*************************************************************}
  119. PROCEDURE ShowProgress;
  120. VAR
  121.     Percent : string[7];
  122. {show the user what percentage of the input we've done - eye candy}
  123. BEGIN
  124.     Str((TotalBytesIn * 100) / InputFileSize : 6 : 1, Percent);
  125.     IF OldPct <> Percent THEN  {this speeds things a bit}
  126.         BEGIN
  127.             OldPct:=Percent;
  128.             FastText('Percentage Completed = ' + Percent, 6, 2);
  129.         END;
  130. END;  {ShowProgress}
  131. {**************************************************************}
  132. PROCEDURE ReadInput (CONST ByteCount : shortint;
  133.                                          VAR ReadString : RLE_Rec_String);
  134. {feed BYTECOUNT bytes from the input file.  A string buffer is used to hold
  135. the file's data to minimize the I/O time spent in the file. The output is a
  136. 0-index-based char array.}
  137. VAR
  138.     BCount    : shortint;
  139. BEGIN
  140.     IF IBufferIndex+ByteCount-1<=ReadResult THEN                {more data in buffer?}
  141.         BEGIN
  142.             IF ByteCount=1 THEN
  143.                 ReadString[0]:=IBuffer[IBufferIndex]
  144.             ELSE
  145.                 Move (IBuffer[IBufferIndex],ReadString[0],ByteCount);
  146.             IBufferIndex := IBufferIndex + ByteCount;
  147.         END
  148.     ELSE
  149.         BEGIN                                                    {no, get more from file}
  150.             IF LastIBuffer THEN
  151.                 EndInput:=true            {last buffer was delivered}
  152.             ELSE
  153.                 BEGIN                     {read another block}
  154.                     BCount:=ByteCount;
  155.                     {if there's anything in the buffer, output the remainder as the 1st
  156.                     chunk of the data requested}
  157.                     IF IBufferIndex<=BufSize THEN      {was the entire buffer used}
  158.                         BEGIN                            {no, there's more in there to give}
  159.                             IF IBufferIndex=BufSize THEN
  160.                                 ReadString[0]:=IBuffer[BufSize]
  161.                             ELSE
  162.                                 Move(IBuffer[IBufferIndex],ReadString[0],Length(IBuffer)-IBufferIndex+1);
  163.  
  164.                             BCount:=BCount-(BufSize-IBufferIndex+1);
  165.                         END; {buffer index <= buffer size}
  166.  
  167.                     {$I-} BlockRead (InputFile, IBuffer[1], BufSize, ReadResult); {$I+}
  168.                     IF (IOResult = EndOfFile) OR (ReadResult<BufSize) THEN
  169.                         LastIBuffer:=true;     {last buffer has been input}
  170.  
  171.                     IF ReadResult>0 THEN
  172.                         BEGIN
  173.                             IBuffer[0]:=Chr(ReadResult);   {set length of string}
  174.  
  175.                             IF BCount=1 THEN               {Asking for only 1 byte}
  176.                                 ReadString[ByteCount-BCount]:=IBuffer[1]    {yes, faster than 1 byte MOVE}
  177.                             ELSE
  178.                                 Move(IBuffer[1],ReadString[ByteCount-BCount],BCount);
  179.  
  180.                             TotalBytesIn:=TotalBytesIn + ReadResult;
  181.                             IBufferIndex := BCount+1;
  182.                         END;  {result>0}
  183.                 END;  {input another block}
  184.         END;  {else}
  185. END;  {ReadRaw}
  186. {*************************************************************}
  187. PROCEDURE Compress;
  188. {Compress the input file by reading it one byte at a time and comparing
  189. that byte to the one previously read.}
  190.  
  191.     {================================================}
  192.     PROCEDURE NewSegment (CONST StringType : SegmentTypes);
  193.     {set the appropriate prefix type; write the string segment and adjust
  194.     the statistics counters.  Lastly insert the latest byte and reset the
  195.     prefix count to 1}
  196.     BEGIN
  197.         CASE StringType OF
  198.             LEN    :
  199.                     BEGIN {prefix byte remains positive < 128}
  200.                         BlockWrite (OutputFile, RLE_Record, RLE_Record.RepeatCount + 1);
  201.                         TotalBytesOut:=TotalBytesOut + RLE_Record.RepeatCount + 1;
  202.                     END;  {LEN}
  203.             RUN    :
  204.                     BEGIN {flip the sign of the prefix byte}
  205.                         RLE_Record.RepeatCount:=RLE_Record.RepeatCount * -1;
  206.                         BlockWrite (OutputFile, RLE_Record, 2);
  207.                         TotalBytesOut:=TotalBytesOut + 2;
  208.                     END;  {RUN}
  209.         END;  {CASE}
  210.  
  211.         Segments:=Segments+1;
  212.         RLE_Record.Data[1]:=CurrentChar;  {set new byte to compare}
  213.         RLE_Record.RepeatCount:=1;        {only one of them so far}
  214.     END;  {NewSegment}
  215.     {================================================}
  216.     FUNCTION ReadRaw : char;
  217.     {feed one byte from the input file.  A string buffer is used to hold
  218.     the file's data to minimize the I/O time spent in the file.}
  219.     BEGIN
  220.         IF IBufferIndex<=ReadRes